package com.bigshen.algorithm.eTwoPointer.solution04TrappingRainWater;

/**
 * 42. Trapping Rain Water
 * Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
 *
 * Example 1:
 * Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * Output: 6
 * Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
 *
 * Example 2:
 * Input: height = [4,2,0,3,2,5]
 * Output: 9
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/trapping-rain-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {

    // 双指针 start、end
    // 左右两边 相比较：
    // 左边高则右指针往左走并计算水滴
    // 右边高则左指针往右走并计算水滴
    public int trap(int[] height) {

        if (null == height || height.length == 0) {
            return 0;
        }

        int total = 0;
        int start = 0;
        int end = height.length - 1;
        int leftHeight = height[start];
        int rightHeight = height[end];

        while (start < end) {
            if (leftHeight < rightHeight) {
                // 左低右高，左边向前走 start-->
                int nextLeftHeight = height[start+1];
                if (nextLeftHeight < leftHeight) {
                    // 下一个比当前低，可以存水
                    total += (leftHeight - nextLeftHeight);
                } else {
                    // 遇到更高的挡板，替换为更高的挡板
                    leftHeight = nextLeftHeight;
                }
                start++;
            } else {
                // 左高右低，右边向后走 <--end
                int nextRightHeight = height[end-1];
                if (nextRightHeight < rightHeight) {
                    // 可以存水
                    total += (rightHeight - nextRightHeight);
                } else {
                    // 遇到更高的挡板，替换为更高的挡板
                    rightHeight = nextRightHeight;
                }
                end--;
            }
        }

        return total;

    }

    public static void main(String[] args) {

        int[] array = {4,2,0,3,2,5};

        System.out.println(new Solution().trap(array));

    }

}
